//
// Created by yewei on 2025/4/29.
//
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>

using namespace std;

#define LEN 100

int isMatch(char a, char b) {
    if ((a == 'A' && b == 'U') || (a == 'U' && b == 'A'))
        return 1;
    if ((a == 'C' && b == 'G') || (a == 'G' && b == 'C'))
        return 1;
    return 0;
}

int RNA_2(char B[LEN], int n) {
    int i, j, k, t;
    int max;
    int C[LEN][LEN] = {0};

    for (k = 5; k <= n - 1; k++) {
        for (i = 1; i <= n - k; i++) {
            j = i + k;
            max = C[i][j - 1]; //1
            for (t = i; t <= j - 4; t++) { //2
                //3
                if (isMatch(B[t], B[j]) && max < C[i][t - 1] + 1 + C[t + 1][j - 1])
                    max = C[i][t - 1] + 1 + C[t + 1][j - 1];
            }
            C[i][j] = max;
            printf("c[%d][%d]=%d--", i, j, C[i][j]);
        }
    }
    return max; //4 或 return c[i-1][j]
}

int main() {
    int n = 9;
    char B[9] = {'A', 'C', 'C', 'G', 'G', 'U', 'A', 'G', 'U'};
//    cout << RNA_2(B, n);
    int max = RNA_2(B, n);
    cout << endl << max;
}